#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<string>

using namespace std;

//set--key模型 key值不可以修改
void test_set1()
{
	set<int> s;
	//排序+去重
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);

	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " " ;
		it++;
	}
	cout << endl;

	//查找
	set<int>::iterator pos = s.find(3);  //时间复杂度为O(logN）
	//set<int>::iterator pos = find(s.begin(),s.end(),3);  //时间复杂度为O(N)

	//删除
	//s.erase(3);  //不存在的数据不会报错
	if(pos!=s.end())
	s.erase(pos);  //不存在的数据会报错

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;


	set<int> s1;
	//排序+去重
	s1.insert(1);
	s1.insert(1);
	s1.insert(2);
	s1.insert(2);
	s1.insert(3);
	s1.insert(4);
	s1.insert(5);

	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;

	//区间的上下限
	//[2,5)
	set<int>::iterator itlow = s1.lower_bound(2);  //  >=2
	set<int>::iterator itup = s1.upper_bound(4);  // >4

	s1.erase(itlow, itup);

	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;

	multiset<int> ss;
	//排序+不去重
    ss.insert(1);
	ss.insert(1);
	ss.insert(2);
	ss.insert(2);
	ss.insert(2);
	ss.insert(3);
	ss.insert(4);
	ss.insert(5);

	for (auto e : ss)
	{
		cout << e << " ";
	}
	cout << endl;

	//删除重复值
	//pair是一个结构体类型
	pair<multiset<int>::const_iterator, multiset<int>::const_iterator> ret;

	//未找到匹配项 两个迭代器都指向被视为位于 key 之后的第一个元素
	ret = ss.equal_range(2);
	multiset<int>::const_iterator begin = ret.first;  // >=2
	multiset<int>::const_iterator end = ret.second;  // >2

	ss.erase(begin, end);
	for (auto e : ss)
	{
		cout << e << " ";
	}
	cout << endl;

}

void test_map1()
{
	map<string, string> m;
	//C++98
	pair<string, string> _pair("insert", "插入");
	m.insert(_pair);

	m.insert(pair<string, string>("erase", "删除"));

	m.insert(make_pair("sort", "排序"));

	//C++11
	m.insert({ "modify","修改" });

	// 不插入，不覆盖
	// 插入过程中，只比较key，value是相同无所谓
	// key已经有了就不插入了
	m.insert(make_pair("insert", "xxxx"));

	map<string, string>::iterator itm = m.begin();
	while (itm != m.end())
	{
		//cout << (*itm).first << ":" << (*itm).second << endl;
		cout << itm->first << ":" << itm->second << endl;
		itm++;
	}
	cout << endl;
	for (const auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	//查找
	map<string, string>::iterator pos = m.find("sort");
	
	//删除:该函数返回删除的元素数
	int ret = m.erase("insert");
	m.erase(pos);
	for (const auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	map<string, string> m1;
	m1.insert({ "insert","插入" });
	m1.insert({ "sort","排序" });
	m1.insert({ "erase","删除" });
	m1.insert({ "modify","修改" });
	//左闭右开["insert","sort")
	map<string, string>::iterator itlow = m1.lower_bound("insert");
	map<string, string>::iterator itup = m1.upper_bound("modify");
	m1.erase(itlow, itup);
	for (const auto& e : m1)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	map<string, string> m2;
	m2.insert({ "insert","插入" });
	m2.insert({ "sort","排序" });
	m2.insert({ "erase","删除" });
	m2.insert({ "modify","修改" });
	pair<map<string,string>::iterator, map<string, string>::iterator> equal_range = m2.equal_range("insert");
	map<string, string>::iterator begin = equal_range.first;
	map<string, string>::iterator end = equal_range.second;
	m2.erase(begin, end);
	for (const auto& e : m2)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

}

//统计水果的次数
void test_map2()
{
	string a[] = { "西瓜","哈密瓜","哈密瓜", "哈密瓜", "哈密瓜", "哈密瓜","西瓜","苹果","苹果" ,"苹果","哈密瓜" };
	map<string, int> countMap;
	/*for (const auto& e : a)
	{
		if (countMap.find(e) == countMap.end())
		{
			countMap.insert({ e,1 });
		}
		else
		{
			countMap.find(e)->second++;
		}
	}*/

	for (const auto& e : a)
	{
		countMap[e]++;
	}

	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}

}

void test_multimap()
{
	//key有了可以继续插入
	multimap<string, string> m;
	m.insert({ "insert","插入" });
	m.insert({ "insert","xxx" });
	m.insert({ "insert","yyy" });
	m.insert({ "sort","排序" });
	m.insert({ "erase","删除" });
	m.insert({ "modify","修改" });
	m.insert({ "modify","zzz" });


	for (const auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	pair<map<string, string>::iterator, map<string, string>::iterator> ret = m.equal_range("insert");
	map<string, string>::iterator begin = ret.first;
	map<string, string>::iterator end = ret.second;
	m.erase(begin, end);
	for (const auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	map<string, string>::iterator itlow = m.lower_bound("modify");
	map<string, string>::iterator itup = m.upper_bound("sort");
	m.erase(itlow, itup);
	for (const auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;


}

int main()
{
	test_set1();
	cout << "------------------------------------------" << endl;

	test_map1();
	cout << "------------------------------------------" << endl;

	test_map2();
	cout << "------------------------------------------" << endl;

	test_multimap();
	cout << "------------------------------------------" << endl;

	return 0;
}
